#include <iostream>
#define N 41
using namespace std;

long long pigs[N];
long long dp[N];

int main()
{
    int T, n;
    pigs[1] = 1;
    pigs[2] = 1;
    pigs[3] = 5;
    pigs[4] = 9;
    pigs[5] = 29;
    dp[1] = 1;
    dp[2] = 0;
    dp[3] = 4;
    dp[4] = 4;
    dp[5] = 20;
    for (int i = 6; i <= 40; i++)
    {
        dp[i] += 4*(dp[i-2] + dp[i-3]+dp[i-4]);
        pigs[i] = pigs[i - 1] + dp[i] - dp[i - 5];
    }
    cin >> T;
    while (T--)
    {
        cin >> n;
        cout << pigs[n] << endl;
    }
    return 0;
}
